1. Field of the Invention
This invention generally relates to methods and systems for solving N-body problems, such as classical molecular dynamics. More specifically, the invention relates to methods and systems for creating a load balanced spatial partitioning of a structured, diffusing system of particles.
2. Background Art
Over the last few years, unprecedented computational resources have been developed, such as the Blue Gene computing system family of computers from the International Business Machines Corporation. These resources may be used to attack, among other issues, grand challenge life sciences problems such as advancing the understanding of biologically important processes, in particular, the mechanisms behind protein folding.
In order to address this goal, attention has been directed to creating a classical molecular dynamics software package for long-time and large-scale molecular simulations. Classical molecular dynamics is predominantly an N-body problem. A standard definition of an n-body problem is as follows:                The n-body problem is the problem of finding, given the initial positions, masses, and velocities of n bodies, their subsequent motions as determined by classical mechanics.        
An N-body problem, for example molecular dynamics (MD), proceeds as a sequence of simulation time steps. At each time step, forces on particles, in MD atoms, are computed; and then the equations of motion are integrated to update the velocities and positions of the particles. In order to compute the forces on the particles, nominally the force between each particle and every other particle is computed, a computational burden of O(n2).
Practically speaking, molecular dynamics programs reduce the O(n2) by cutting off pair interactions at some distance. However for many scientifically relevant molecular systems, the computational burden due to the particle pair interactions remains large. In order to reach scientifically relevant simulation times, parallel computers are required to compute particle pair interactions rapidly.